#include <tuple>
#include <algorithm>

using namespace std;

template <typename T>
struct TreeNode
{
    T val;
    TreeNode<T> *left;
    TreeNode<T> *right;
    int height;
};

class AVLTree
{
public:
    AVLTree();
    virtual ~AVLTree(){};
    void Insert(int val);
    void Delete(int val);
    tuple<bool, TreeNode<int> *> Search(int val);
    void InOrderTraversal()const;
    int Size() const;
    int Depth() const;

private:
    TreeNode<int> *root;
    int size, depth;
    int getHeight(TreeNode<int> *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        return root->height;
    }
    int getBalanceFactor(TreeNode<int> *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        return this->getHeight(root->left) - this->getHeight(root->right);
    }
    TreeNode<int> *createNode(int val)
    {
        TreeNode<int> *node = new TreeNode<int>();
        node->val = val;
        node->left = nullptr;
        node->right = nullptr;
        node->height = 1;
        return node;
    }
    void updateHeight(TreeNode<int> *root)
    {
        root->height = max(this->getHeight(root->left), this->getHeight(root->right)) + 1;
    };
    TreeNode<int> *rightRotate(TreeNode<int> *root)
    {
        TreeNode<int> *newRoot = root->left;
        TreeNode<int> *tmp = newRoot->right;
        newRoot->right = root;
        root->left = tmp;
        this->updateHeight(root);
        this->updateHeight(newRoot);
        return newRoot;
    }
    TreeNode<int> *leftRotate(TreeNode<int> *root)
    {
        TreeNode<int> *newRoot = root->right;
        TreeNode<int> *tmp = newRoot->left;
        newRoot->left = root;
        root->right = tmp;
        this->updateHeight(root);
        this->updateHeight(newRoot);
        return newRoot;
    }
    TreeNode<int> *insertNode(TreeNode<int> *root, int val)
    {
        if (root == nullptr)
        {
            return this->createNode(val);
        }
        if (val < root->val)
        {
            root->left = this->insertNode(root->left, val);
        }
        else if (val > root->val)
        {
            root->right = this->insertNode(root->right, val);
        }
        else
        {
            return root;
        }
        this->updateHeight(root);
        int bf = this->getBalanceFactor(root);
        if (bf > 1 && val < root->left->val)
        {
            return this->rightRotate(root);
        }
        if (bf < -1 && val > root->right->val)
        {
            return this->leftRotate(root);
        }
        if (bf > 1 && val > root->left->val)
        {
            root->left = this->leftRotate(root->left);
            return this->rightRotate(root);
        }
        if (bf < -1 && val < root->right->val)
        {
            root->right = this->rightRotate(root->right);
            return this->leftRotate(root);
        }
        return root;
    }
    TreeNode<int> *minNode(TreeNode<int> *root)
    {
        TreeNode<int> *node = root;
        while (node->left != nullptr)
        {
            node = node->left;
        }
        return node;
    }
    TreeNode<int> *deleteNode(TreeNode<int> *root, int val)
    {
        if (root == nullptr)
        {
            return root;
        }
        if (val < root->val)
        {
            root->left = this->deleteNode(root->left, val);
        }
        else if (val > root->val)
        {
            root->right = this->deleteNode(root->right, val);
        }
        else
        {
            if ((root->left == nullptr) || (root->right == nullptr))
            {
                TreeNode<int> *tmp = root->left ? root->left : root->right;
                if (tmp == nullptr)
                {
                    tmp = root;
                    root = nullptr;
                }
                else
                {
                    *root = *tmp;
                }
                delete tmp;
            }
            else
            {
                TreeNode<int> *tmp = this->minNode(root->right);
                root->val = tmp->val;
                root->right = this->deleteNode(root->right, tmp->val);
            }
        }
        if (root == nullptr)
        {
            return root;
        }
        this->updateHeight(root);
        int bf = this->getBalanceFactor(root);
        if (bf > 1 && this->getBalanceFactor(root->left) >= 0)
        {
            return this->rightRotate(root);
        }
        if (bf > 1 && this->getBalanceFactor(root->left) < 0)
        {
            root->left = this->leftRotate(root->left);
            return this->rightRotate(root);
        }
        if (bf < -1 && this->getBalanceFactor(root->right) <= 0)
        {
            return this->leftRotate(root);
        }
        if (bf < -1 && this->getBalanceFactor(root->right) > 0)
        {
            root->right = this->rightRotate(root->right);
            return this->leftRotate(root);
        }
        return root;
    }
    TreeNode<int> *searchNode(TreeNode<int> *root, int val)
    {
        if (root == nullptr)
        {
            return root;
        }
        if (root->val > val)
        {
            return this->searchNode(root->left, val);
        }
        if (root->val < val)
        {
            return this->searchNode(root->right, val);
        }
        return root;
    }
};
